package com.algorithm.ch1.cjm.tree;

import com.algorithm.ch1.cjm.tree.model.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 二叉树的最大深度
 * 给定一个二叉树，找出其最大深度。
 * <p>
 * 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
 * <p>
 * 说明: 叶子节点是指没有子节点的节点。
 * <p>
 * 示例：
 * 给定二叉树 [3,9,20,null,null,15,7]，
 * <p>
 * 3
 * / \
 * 9  20
 * /  \
 * 15   7
 * 返回它的最大深度 3
 */
public class MaxDepth {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        TreeNode node1 = new TreeNode(9);
        TreeNode node2 = new TreeNode(20);
        TreeNode node3 = new TreeNode(15);
        TreeNode node4 = new TreeNode(7);

        root.left = node1;
        root.right = node2;
        node1.right = node3;
        node2.right = node4;

        MaxDepth ma = new MaxDepth();
        int i = ma.maxDepth1(root);

        System.out.println(i);
    }

    public int maxDepth1(TreeNode root){

        if(root == null){
            return 0;
        }

        int leftDepth = maxDepth1(root.left);
        int rightDepth = maxDepth1(root.right);

        System.out.println(leftDepth + " | " + rightDepth);

        return Math.max(leftDepth, rightDepth) + 1;
    }

    /**
     * 第一版
     * T(n) = 不太会
     * @param root
     * @return
     */
    public int maxDepth(TreeNode root) {

        if(root == null){
            return 0;
        }

        int depth = 1;

        while (true){

            List<TreeNode> list = getTreeNodeByDepth(depth, root);

            if(list.size() == 0){
                depth --;
                break;
            }
            depth ++;
        }

        return depth;
    }

    private List<TreeNode> getTreeNodeByDepth(int depth, TreeNode root){

        List<TreeNode> list = new ArrayList<>();

        if(depth == 1){
            list.add(root);
        }else {
            List<TreeNode> list1 = getTreeNodeByDepth(depth -1, root);

            for(TreeNode treeNode: list1){

                if(treeNode.left != null){
                    list.add(treeNode.left);
                }
                if(treeNode.right != null){
                    list.add(treeNode.right);
                }
            }
        }
        return list;
    }

}
